public class TestBinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

//    一种最简单的二叉树的创建方式，返回二叉树的根节点
    public TreeNode createTree() {
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left=B;
        A.right=C;
        B.left=D;
        B.right=E;
        E.right=H;
        C.left=F;
        C.right=G;

        return A;
    }

//    前序遍历
    void preOrder(TreeNode root) {
        if(root==null)return;
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

//    中序遍历
    void inOrder(TreeNode root) {
        if(root==null)return;
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }

//    后序遍历
    void postOrder(TreeNode root) {
        if(root==null)return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }

//    求树节点总数
    //子问题思路
    public int size(TreeNode root) {
        if(root==null)return 0;
        return size(root.left)+size(root.right)+1;
    }

    public static int nodeSize;
    //遍历思路
    public void size2(TreeNode root) {
        if(root==null)return;
        nodeSize++;
        size2(root.left);
        size2(root.right);
    }

//    获取叶子结点个数
    //子问题思路
    public int getLeafNode(TreeNode root) {
        if(root==null)return 0;
        if(root.left==null && root.right==null) {
            return 1;
        }
        return getLeafNode(root.left)+getLeafNode(root.right);
    }
    //遍历思路
    public int leafSize;
    public void getLeafNode2(TreeNode root) {
        if(root==null)return;
        if(root.left==null && root.right==null)leafSize++;
        getLeafNode2(root.left);
        getLeafNode2(root.right);
    }

//    获取第k层节点的个数
    public int getKLevelNode(TreeNode root,int k) {
        if(root==null)return 0;
        if(k==1)return 1;
        return getKLevelNode(root.left,k-1)+
                getKLevelNode(root.right,k-1);
    }

//    求当前树的高度
    public int getHeight(TreeNode root) {
        if(root==null)return 0;
        int leftHeight=getHeight(root.left);
        int rightHeight=getHeight(root.right);
        return leftHeight>rightHeight?
                leftHeight+1:
                rightHeight+1;
    }

//    遍历二叉树找到val所在的节点
    public TreeNode find(TreeNode root,char val) {
        if(root==null)return null;
        if(root.val==val)return root;
        if(find(root.left,val)!=null)return root.left;
        if(find(root.right,val)!=null) return root.right;
        return null;
    }


    /**
     * 时间复杂度为 O(m*n)
     * @param root m
     * @param subRoot n
     * @return
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // 递归过程中root可能为空，所以要加上
        if(root==null)return false;

        // 1.判断两树是否完全相同
        if(isSameTree(root,subRoot))return true;

        // 2.与左右子树比较
        if(isSubtree(root.left,subRoot)) return true;

        if(isSubtree(root.right,subRoot))return true;

        return false;
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        //1. 一个为空，一个不为空
        if(p!=null && q==null || p==null && q!=null) {
            return false;
        }

        // 2. 两个都是空
        if(p==null && q==null) return true;

        // 3. 判断值是否相等
        if(p.val!=q.val) return false;

        // 4. 此时代表2两个节点都不为空，且值相等
        // 然后递归判断左右子树是否相同
        return isSameTree(p.left,q.left)&& isSameTree(p.right,q.right);
    }


    /**
     * 时间复杂度为：O(n^2)
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        if(root==null) return true;

        int leftH=maxDepth(root.left);
        int rightH=maxDepth(root.right);

        return Math.abs(leftH-rightH)<=1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }

    public int maxDepth(TreeNode root) {
        if(root==null)return 0;
        int leftHeight=maxDepth(root.left);
        int rightHeight=maxDepth(root.right);
        return leftHeight>rightHeight? leftHeight+1 :rightHeight+1;
    }


    public boolean isBalanced2(TreeNode root) {
        if(root==null) return true;

        return maxDepth(root)>=1;
    }

    public int maxDepth2(TreeNode root) {
        if(root==null)return 0;
        int leftHeight=maxDepth(root.left);
        if(leftHeight<0)return -1;

        int rightHeight=maxDepth(root.right);
        if(rightHeight<0)return -1;

        if(Math.abs(leftHeight-rightHeight)<=1) {
            return Math.max(leftHeight,rightHeight)+1;
        }else {
            return -1;
        }
    }

    public boolean isSymmetric(TreeNode root) {
        return isSymmetricChild(root.left,root.right);
    }

    public boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
        // 1. 检查结构
        if(leftTree!=null && rightTree ==null || leftTree==null && rightTree !=null) {
            return false;
        }

        if(leftTree==null && rightTree==null)return true;

        if(leftTree.val!=rightTree.val) return false;

        return isSymmetricChild(leftTree.left,rightTree.right) &&
                isSymmetricChild(leftTree.right,rightTree.left);
    }

}
